#include <iostream>
#include <string>
#include <set>
#include <map>
#include <ctime>
#include "avltree.hpp"
#include "rbtree.old.hpp"
#include "rbtree.hpp"
#include "map.hpp"
#include "set.hpp"

using namespace std;

void test_set_1()
{
    set<int> s1;
    s1.insert(3);
    s1.insert(4);
    s1.insert(4);
    s1.insert(8);
    s1.insert(1);
    s1.insert(9);
    s1.insert(9);
    s1.insert(2);

    set<int>::iterator it = s1.begin();
    while (it != s1.end())
    {
        // (*it)++;
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    // 1 2 3 4 8 9

    for (auto& e : s1)
    {
        // e += 1;
        cout << e << " ";
    }
    cout << endl;

    // int x;
    // while (cin >> x)
    // {
    //     // if (s1.find(x) != s1.end())
    //     if (s1.count(x))
    //     {
    //         cout << "ok" << endl;
    //     }
    //     else
    //     {
    //         cout << "unkown" << endl;
    //     }
    // }
}

void test_set_2()
{
    std::multiset<int> s1;
    s1.insert(3);
    s1.insert(4);
    s1.insert(4);
    s1.insert(8);
    s1.insert(8);
    s1.insert(1);
    s1.insert(9);
    s1.insert(9);
    s1.insert(2);

    std::multiset<int>::iterator it = s1.begin();
    while (it != s1.end())
    {
        // (*it)++;
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    std::multiset<int>::iterator pos = s1.find(8);
    while (pos != s1.end() && *pos == 8)
    {
        cout << *pos << " ";
        ++pos;
    }
    // 8 8
}

void test_map_1()
{
    map<string, string> dict;

    dict.insert(pair<string, string>("i", "wo"));
    dict.insert(make_pair("is", "shi"));
    dict.insert({"sort", "paixu"});
    auto ret = dict.insert({"sort", "[[paixu]]"});
    // pair<iterator, bool>
    cout <<(ret.first)->first << (ret.first)->second << ret.second << endl;
    cout << (*ret.first).first << endl;

    string str;
    while (cin >> str)
    {
        map<string, string>::iterator it = dict.find(str);
        if (it != dict.end())
        {
            cout << it->first << "-" << it->second << endl;
        }
    }
}

void test_map_2()
{
    string arr[]
        = {"xg","xg","pg","xg","pg","pg","xg","pg","xj","pg","xj","li"};

    map<string, int> count_map;
    for (auto& e : arr)
    {
        map<string, int>::iterator ret = count_map.find(e);
        if (ret == count_map.end())
        {
            count_map.insert(make_pair(e, 1));
        }
        else
        {
            ret->second++;
        }
    }

    for (auto& e : arr)
    {
        count_map[e]++;
    }

    count_map["tz"];
    cout << count_map["pg"];
    count_map["pg"] = 111;
    count_map["mht"] = 888;

    for (auto& kv: count_map)
    {
        cout << kv.first << ": " << kv.second << endl;
    }
}

void test_avl_1()
{
    int a[] = {16,3,7,11,9,26,18,14,15};
    int b[] = {4,2,6,1,3,5,15,7,16,14};

    avl_tree<int, int> t1;
    avl_tree<int, int> t2;

    for (auto e : a)
    {
        t1.insert(make_pair(e, e));
    }

    for (auto e : b)
    {
        t2.insert((make_pair(e, e)));
    }

    t1.inorder();
    t2.inorder();

    cout << "------------------------" << endl;

    cout << t1.is_balance() << endl;
    cout << t2.is_balance() << endl;
}

void test_avl_2()
{
    srand((size_t)time(nullptr));
    const size_t N = 10000;

    avl_tree<int, int> t;
    for (size_t i = 0; i < N; i++)
    {
        int x = rand();
        t.insert(make_pair(x, x));
    }

    cout << t.is_balance() << endl;
}

void test_rbt_1()
{
    int a[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
    int b[] = {4, 2, 6, 1, 3, 5, 15, 7, 16, 14};

    old::rb_tree<int, int> t1;
    old::rb_tree<int, int> t2;

    for (auto e : a)
    {
        t1.insert(make_pair(e, e));
    }

    for (auto e : b)
    {
        t2.insert(make_pair(e, e));
    }

    t1.inorder();
    t2.inorder();

    cout << "------------------------" << endl;

    cout << t1.is_rbtree() << endl;
    cout << t2.is_rbtree() << endl;
}

void test_rbt_2()
{
    srand((size_t)time(nullptr));
    const size_t N = 10000;

    old::rb_tree<int, int> t;
    for (size_t i = 0; i < N; i++)
    {
        int x = rand();
        t.insert(make_pair(x, x));
    }

    cout << t.is_rbtree() << endl;
}

int main()
{
    // test_set_1();
    // test_set_2();
    // test_map_1();
    // test_map_2();

    // test_avl_1();
    // test_avl_2();
    // test_rbt_1();
    // test_rbt_2();

    // test::test_map_1();
    // test::test_map_2();
    // test::test_map_3();
    // test::test_set_1();
    // test::test_set_2();

    return 0;
}